package _08_DFS_BFS;

import com.sun.org.apache.bcel.internal.generic.NEW;
import util.Calculator;

import java.util.ArrayList;
import java.util.List;

public class _282_给表达式添加运算符 {


    public static void main(String[] args) {

        String str = "12345";

        _282_给表达式添加运算符 v = new _282_给表达式添加运算符();
        List<String> strings = v.addOperators(str, 15);
        for (String string : strings) {
            double va = Calculator.conversion(string);
            if (va != 45) {
                System.out.println(va);
                System.out.println(string);
                System.out.println("---------------------");
            }
        }
    }

    private List<String> results = new ArrayList<>();

    private List<List<String>> containers = new ArrayList<>();

    private int target;

    public List<String> addOperators(String num, int target) {
        this.target = target;
        // 如何分割字符串
        char[] chars = num.toCharArray();
        dfs(chars, new ArrayList<>(), 0, chars.length);
        for (List<String> list : containers) {

            String str = list.get(0);
            // 设置访问数组
            Long cur = Long.parseLong(str);
            StringBuilder sb = new StringBuilder();
            sb.append(cur);
            dfs(list, 1, cur, cur, sb, '+');
        }
        return results;
    }

    private void dfs(List<String> list, int index, long prev, long total, StringBuilder sb, int isAddOrSub) {
        if (index == list.size()) {
            if (total == target) {
                results.add(sb.toString());
            }
            return;
        }
        String s = list.get(index);
        int cLen = s.length() + 1;
        long cur = Long.parseLong(s);
        // +
        sb.append('+').append(cur);
        dfs(list, index + 1, cur, total + cur, sb, '+');
        sb.delete(sb.length() - cLen, sb.length());

        // -
        sb.append('-').append(cur);
        dfs(list, index + 1, cur, total - cur, sb, '-');
        sb.delete(sb.length() - cLen, sb.length());

        // *
        sb.append('*').append(cur);
        long result = total * cur;
        if (isAddOrSub == '+') {
            result = total - prev + (prev * cur);
        } else if (isAddOrSub == '-') {
            result = total + prev - (prev * cur);
        }
        dfs(list, index + 1, prev * cur, result, sb, isAddOrSub);
        sb.delete(sb.length() - cLen, sb.length());
    }

    public void dfs(char[] str, List<String> list, int begin, int end) {
        if (begin == end) {
            containers.add(new ArrayList<>(list));
            return;
        }
        for (int i = begin; i < end; i++) {
            String s = new String(str, begin, i - begin + 1);
            if ((s.length() == 1 || !s.startsWith("0"))) {
                list.add(s);
                dfs(str, list, i + 1, end);
                list.remove(list.size() - 1);
            }
        }
    }
}
